The present invention relates to a recovery path designing circuit, a method and a program thereof for designing an alternative path in a pre-establishing-type failure-detected end switching system.
As a conventional communication network designing method, for example, there has been proposed a recovery path designing method for a path end switching system in which a path is switched at the origin thereof by Yijun Xiong and Lorne Mason, xe2x80x9cRestoration strategies and spare capacity requirements in self-healing ATM networksxe2x80x9d, INFOCOM""97, April 1997.
FIG. 1 is a diagram showing an example of a result of design obtained on the basis of the conventional designing method. In FIG. 1, reference marks n1 to n8 represent nodes, and reference marks p1 and p2 denote paths. The p1 is a primary path, and the p2 is a recovery path. Each line between adjacent two nodes represents a link. These links are expressed as link (n1, n2) and the like. While depicted with one line in FIG. 1, each link is bi-directional. For example, the link (n1, n2) includes two links in the opposite directions: from n1 to n2; and from n2 to n1. It should be noted that any number of links may be present between adjacent two nodes.
In this example in FIG. 1, the alternative path p2 is set for the primary path p1. In case of actual failure, the node n1 at one end of the path is informed of the failure, and switches the route from the primary path p1 to the alternative path p2. For example, when failure occurs on the link (n3, n4), the node n3 detects the failure and sends a message of the failure occurrence to the node n1. When receiving the message, the node n1 switches the route to the recovery path p2.
In the following, another prior arts related to the present invention are mentioned. In Japanese Patent Application Laid-Open No. 2000-22750, the applicant of the present invention has disclosed a technique, in a multipoint communication network designing method, to design a link capacity and a node capacity in a communication network on the premise of variation of traffic demands. This application does not directly teach, but touches on, the recovery path designing method for a pre-establishing-type failure detecting end switching system.
In Japanese Patent Application Laid-Open No. HEI 11-215124, the applicant has disclosed a technique to accommodate traffic even if demand patterns are changed to some extent.
In Japanese Patent Application Laid-Open No. 2001-36574, the applicant has disclosed a technique, when communication between an ingress node and an egress node of a network is performed on a communication line having tree structure, to build a communication link having tree structure with the minimum number of branches, which accommodates paths between a given entrance node and exit node.
Additionally, in Japanese Patent Application Laid-Open No. 2002-57676, the applicant has disclosed a technique to permit arbitrary communication within a given range by providing the amount of data traffic flowing in through an ingress node and the amount of data traffic flowing out from an egress node.
Compared to the path end switching system, in a failure-detected end switching system, there is no need to notify a failure occurrence because a node that has detected the failure switches a route, thus enabling faster failure recovery. However, a plurality of recovery paths are necessary for one primary path. Thereby, unless the recovery paths are set so as to effectively share the resources for recovery, a great amount of resources is to be required.
The method proposed by Yijun Xiong and Lorne Mason is premised on the path end switching system. In this method, it is impossible to design recovery paths on the basis of failure-detected end switching, and an efficient recovery path designing method has been sought.
It is therefore an object of the present invention to provide a recovery path designing circuit, a method and a program thereof capable of reducing necessary resources as much as possible when forming recovery paths on a pre-establishing-type failure-detected end switching system.
According to a first aspect of the present invention, for achieving the object mentioned above, there is provided a recovery path designing circuit for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, comprising:
an optimization reference generating means for setting an objective function to minimize a link cost;
a recovery path forming condition generating means for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating means for generating a constraint expression to calculate a link capacity required of the respective links;
a link accommodating condition generating means for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating means for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing means for solving integer programming problems expressed by the objective function set by the optimization reference generating means and constraint expressions generated by the recovery path forming condition generating means, the link capacity calculating condition generating means, the link accommodating condition generating means, and the forbidden link and node setting condition generating means.
According to a second aspect of the present invention, in the first aspect, the optimization reference generating means sets an objective function to minimize a link metric and a path metric in addition to the minimization of the link cost.
According to a third aspect of the present invention, there is provided a recovery path designing circuit for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, comprising:
an optimization reference generating means for setting an objective function to minimize a maximum link load;
a recovery path forming condition generating means for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating means for generating a constraint expression to calculate a link capacity required of the respective links and the maximum link load;
a link accommodating condition generating means for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating means for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing means for solving integer programming problems expressed by the objective function set by the optimization reference generating means and constraint expressions generated by the recovery path forming condition generating means, the link capacity calculating condition generating means, the link accommodating condition generating means, and the forbidden link and node setting condition generating means.
According to a fourth aspect of the present invention, in one of the first to third aspects, the link capacity calculating condition generating means generates a constraint expression to calculate, with respect to each state, a link capacity in the case where a primary path and a recovery path share their necessary resources.
According to a fifth aspect of the present invention, in one of the first to third aspects, the link capacity calculating condition generating means generates a constraint expression to calculate, with respect to each traffic, a link capacity in the case where recovery paths of one primary path share their necessary resources.
According to a sixth aspect of the present invention, in one of the first to third aspects, the link capacity calculating condition generating means generates a constraint expression to calculate a link capacity in the case where each of all paths is provided with dedicated resources.
According to a seventh aspect of the present invention, there is provided a recovery path designing method for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, comprising:
an optimization reference generating step for setting an objective function to minimize a link cost;
a recovery path forming condition generating step for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating step for generating a constraint expression to calculate a link capacity required of the respective links;
a link accommodating condition generating step for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating step for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing step for solving integer programming problems expressed by the objective function set at the optimization reference generating step and constraint expressions generated at the recovery path forming condition generating step, the link capacity calculating condition generating step, the link accommodating condition generating step, and the forbidden link and node setting condition generating step.
According to an eighth aspect of the present invention, in the seventh aspect, an objective function to minimize a link metric and a path metric is set at the optimization reference generating step in addition to the minimization of the link cost.
According to a ninth aspect of the present invention, there is provided a recovery path designing method for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, comprising:
an optimization reference generating step for setting an objective function to minimize a maximum link load;
a recovery path forming condition generating step for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating step for generating a constraint expression to calculate a link capacity required of the respective links and the maximum link load;
a link accommodating condition generating step for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating step for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing step for solving integer programming problems expressed by the objective function set at the optimization reference generating step and constraint expressions generated at the recovery path forming condition generating step, the link capacity calculating condition generating step, the link accommodating condition generating step, and the forbidden link and node setting condition generating step.
According to a tenth aspect of the present invention, in one of the seventh to ninth aspects, a constraint expression to calculate, with respect to each state, a link capacity in the case where a primary path and a recovery path share their necessary resources is generated at the link capacity calculating condition generating step.
According to an eleventh aspect of the present invention, in one of the seventh to ninth aspects, a constraint expression to calculate, with respect to each traffic, a link capacity in the case where recovery paths of one primary path share their necessary resources is generated at the link capacity calculating condition generating step.
According to a twelfth aspect of the present invention, in one of the seventh to ninth aspects, a constraint expression to calculate a link capacity in the case where each of all paths is provided with dedicated resources is generated at the link capacity calculating condition generating step.
According to a thirteenth aspect of the present invention, there is provided a computer-readable recovery path designing program for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, to have a computer execute:
an optimization reference generating process for setting an objective function to minimize a link cost;
a recovery path forming condition generating process for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating process for generating a constraint expression to calculate a link capacity required of the respective links;
a link accommodating condition generating process for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating process for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing process for solving integer programming problems expressed by the objective function set in the optimization reference generating process and constraint expressions generated in the recovery path forming condition generating process, the link capacity calculating condition generating process, the link accommodating condition generating process, and the forbidden link and node setting condition generating process.
According to a fourteenth aspect of the present invention, in the thirteenth aspect, an objective function to minimize a link metric and a path metric is set in the optimization reference generating process in addition to the minimization of the link cost.
According to a fifteenth aspect of the present invention, there is provided a recovery path designing program for designing recovery paths in a multipoint communication network including a plurality of nodes and links that connect the nodes, which employs a pre-establishing-type failure-detected end switching system in which alternate paths for respective primary paths are pre-established and a node that has detected a failure switches the route from a primary path to a recovery path, to have a computer execute:
an optimization reference generating process for setting an objective function to minimize a maximum link load;
a recovery path forming condition generating process for generating a constraint expression to form a recovery path from a switching start node to an Egress node;
a link capacity calculating condition generating process for generating a constraint expression to calculate a link capacity required of the respective links and the maximum link load;
a link accommodating condition generating process for generating a constraint expression to accommodate the link capacity within a range of a given link capacity;
a forbidden link and node setting condition generating process for generating constraint expressions to set at least one unavailable forbidden node and link with respect to each recovery path; and
an optimizing process for solving integer programming problems expressed by the objective function set in the optimization reference generating process and constraint expressions generated in the recovery path forming condition generating process, the link capacity calculating condition generating process, the link accommodating condition generating process, and the forbidden link and node setting condition generating process.
According to a sixteenth aspect of the present invention, in one of the thirteenth to fifteenth aspects, a constraint expression to calculate, with respect to each state, a link capacity in the case where a primary path and a recovery path share their necessary resources is generated in the link capacity calculating condition generating process.
According to a seventeenth aspect of the present invention, in one of the thirteenth to fifteenth aspects, a constraint expression to calculate, with respect to each traffic, a link capacity in the case where recovery paths of one primary path share their necessary resources is generated in the link capacity calculating condition generating process.
According to an eighteenth aspect of the present invention, in one of the thirteenth to fifteenth aspects, a constraint expression to calculate a link capacity in the case where each of all paths is provided with dedicated resources is generated in the link capacity calculating condition generating process.